package com.monkeyboy.list;

import com.monkeyboy.ListNode;

/**
 * 链表中倒数第K个节点
 * 解题思路：用逆序思维
 * 用两个指针，第二个先走K个节点，到第K个节点的时候第一个指针再走，等第二个到达结尾时候第一个指的位置就是倒数第K个节点
 * 把倒数第K个看做是正数的第几个（思维上把尾端看做是起点走了K个），然后剩下的个数+上K个节点就是整个链表的长度
 * <p>
 * 该题目可以衍生出删除倒数第K个节点
 *
 * @Author Gavin
 * @date 2021.04.03 10:24
 */
public class List04 {

    public static ListNode delListNode(ListNode head, int k) {
        ListNode p = head;
        int c = 1;
        if (k <= 0 || head == null) {
            return null;
        }
        while (head != null) {
            if (c > k) {
                p = p.next;
            }
            head = head.next;
            c++;//head为null的时候会多加一次1,下面判断需要减去
        }
        System.out.println(c);
        if (c - 1 < k) {//小于K说明K的长度超过链表长度了，逆序思维想一下（正序K只有超出链表长度了c每次循环加1的值是不能超过K的）
            return null;
        }
        return p;
    }
    //类似的写法
    public ListNode FindKthToTail(ListNode head, int k) {
        if (head == null)
            return null;
        ListNode P1 = head;
        while (P1 != null && k-- > 0)
            P1 = P1.next;
        if (k > 0)
            return null;
        ListNode P2 = head;
        while (P1 != null) {
            P1 = P1.next;
            P2 = P2.next;
        }
        return P2;
    }
    public static void main(String[] args) {
    }
}
